package com.acyouzi.leetcode.math;

/**
 * 17/9/16 10:42
 *
 * @author sunxu
 */
public class MaximumSwap {
  public int maximumSwap(int num) {
    String tmp = Integer.toString(num);
    char max = '0';
    int[] dp = new int[tmp.length()+1];
    dp[tmp.length()] = tmp.length()-1;
    for (int i = tmp.length()-1; i >= 0; i--) {
      if (max < tmp.charAt(i)){
        dp[i] = i;
        max = tmp.charAt(i);
      } else {
        dp[i] = dp[i+1];
      }
    }
    char[] arr = tmp.toCharArray();
    for (int i = 0; i < tmp.length(); i++) {
      if (dp[i] != i && tmp.charAt(i) != tmp.charAt(dp[i])){
        char c = arr[i];
        arr[i] = arr[dp[i]];
        arr[dp[i]] = c;
        break;
      }
    }
    return Integer.parseInt(String.valueOf(arr));
  }
}
